Market adoption of wireless LAN (WLAN) technology has exploded, as users from a wide range of backgrounds and vertical industries have brought this technology into their homes, offices, and increasingly into the public air space. This inflection point has highlighted not only the limitations of earlier-generation systems, but also the changing role that WLAN technology now plays in people's work and lifestyles, across the globe. Indeed, WLANs are rapidly changing from convenience networks to business-critical networks. Increasingly, users are depending on WLANs to improve the timeliness and productivity of their communications and applications, and in doing so, require greater visibility, security, management, and performance from their networks.
Wireless mesh networks have become increasingly popular. A typical wireless mesh network consists of mesh access points (e.g., Cisco SkyCaptain mesh access points) and wireless clients. To construct self-forming and self-healing multi-hop Wireless mesh networks, each mesh access point finds a route back to the root node. Thus, a routing protocol is essential for the operations of wireless mesh networks.
Traditionally, routing protocol designs follow a strict layered approach, where routing decisions are made based only on information available at the network layer. For instance, many routing protocols for wireless mesh networks use minimum hop counts as the routing metric. A hop count is the number of routing nodes (also referred to as mesh access points, links, or hops) through which a packet travels to reach the root node. While utilizing hop count as a routing metric works well in wired networks, such an approach may suffer from performance degradation in wireless networks, especially in multi-hop wireless mesh networks. Two factors contribute to such performance degradation: 1) wireless links are versatile and interference is time-varying; and 2) contention based wireless media access control (MAC) protocols introduce uncertainties in the system performance. If only network layer information such as the hop count is considered, the resulting routing configuration may cause some routing nodes in the mesh to be heavily congested and thus may adversely affect end-to-end throughput.
In addition, the IEEE Communications Magazine has been actively publishing tutorial papers on mesh networks, routing over mesh networks, QoS routing, load balancing routing, and the metrics used therein. However, such metrics presently do not include end-to-end packet delivery ratio. Some routing protocols use signal-to-noise ratio (SNR) as a routing metric. However, one problem with merely using SNR as a routing metric is that it does not take into account inter-hop interference, congestion level, and hop count. Some routing protocols may combine SNR and hop count but such a combination still does not solve the congestion and interference problem.
A problem with existing routing protocols is that they fail to choose routes with the maximum end-to-end throughput. For instance, a metric may view a two-hop route with high SNR as better than a one-hop route with medium SNR, but this does not maximize end-to-end throughput. Furthermore, routing decisions based on SNR are generally approximated by being “too poor” or “good enough.” As such, once the “good enough” SNR state is reached, there is no strong correlation between packet delivery probability and SNR, which in turn implies that SNR may not be a good predictive tool. This feature is recognized by the nonlinear SNR mapping found in the “Ease” metric. The mapping resembles a smoothed binary decision. In the “zero” region, the mapping is near zero then steeply rises towards the transition point. In the “one” region, the mapping climbs much more slowly. However, presumably for implementation ease, the shape of the mapping near the transition region does not closely match the packet delivery probability shape.
Cross-layer design techniques have been widely applied to many areas of routing, such as quality of service (QoS) routing, load balancing routing, power-aware routing, etc. In mobile ad hoc networks (MANET), load balancing routing is often combined with QoS routing because voice and video applications utilize the User Datagram Protocol (UDP) for packet delivery. Since UDP does not have inherent flow control and congestion control schemes, load balancing to avoid congestion becomes a challenging problem. The most advanced and well-studied approach is to utilize multiple paths for routing, where two or more routes are set up simultaneously between the source routing node and the destination root node. This allows traffic to flow from source routing node to the root node on all available routes. The source routing node determines what percentage of a flow can be routed to each route. When one route experiences congestion, the source routing node is notified, and the congested route is then assigned a lesser percentage of the total traffic flow. Even though this type of multiple-path load balancing approach is robust against congestion, it requires a more sophisticated routing scheme, which increases implementation complexity and cost. In addition, care has to be taken at the end routing nodes to synchronize flows on different routes. Furthermore, the out-of-order packets may have to be re-arranged at the destination.
An alternative way to achieve load balancing is to allow congested routing nodes to transmit control packets to inform their neighboring routing nodes of the congestion situation. This idea was first proposed by He, Stankovic, Lu, and Abdelzaher to solve the congestion problem in wireless sensor networks. Because wireless sensor networks share the same topology as wireless mesh networks, this idea has also been adopted to solve the congestion problem in wireless mesh networks. The basic procedure operates as follows: Each routing node monitors its own congestion level. When the congestion level is above a certain threshold, the load balancing procedure is triggered and a “back-pressure” packet is sent to neighboring routing nodes. Upon receiving the back-pressure packet, a routing node takes appropriate steps to help reduce congestion until being further notified. Utilizing back-pressure routing, a routing node re-routes its packets through other neighboring routing nodes if its downstream routing node on the current route experiences congestion. A problem with the back-pressure routing scheme is that it is primarily directed to avoiding congestion rather than to achieving maximum end-to-end throughput.
An intra-mesh congestion control protocol proposed by Intel Corporation® utilizes a metric based on local queue size to monitor congestion. When the backpressure builds up significantly at the local routing node, the routing node informs its upstream neighbors by sending “Congestion Control Request” messages so that the recipient routing nodes can decrease their transmission rate accordingly. Upon receiving the back-pressure packet, the upstream routing nodes do not choose a different route to transmit. Instead, they may have to transmit at the reduced rate during an extended period. Consequently, the end-to-end throughput may be reduced.
Other load-balancing routing protocols have also been proposed for wireless sensor networks. However, in sensor networks, power preservation is the main goal whereas achieving higher end-to-end throughput is less important.
In light of the foregoing, a need in the art exists for methods, apparatuses, and systems that address the foregoing problems and that facilitate load balancing in wireless mesh networks. Embodiments of the present invention substantially fulfill this need.